{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if it is Possible to Split Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canSplitArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断是否能拆分数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的数组 <code>nums</code> 和一个整数 <code>m</code> 。请你判断能否执行一系列操作，将数组拆分成 <code>n</code> 个 <strong>非空 </strong>数组。</p>\n",
    "\n",
    "<p>在每一步操作中，你可以选择一个 <strong>长度至少为 2</strong> 的现有数组（之前步骤的结果） 并将其拆分成 <strong>2</strong> 个子数组，而得到的 <strong>每个</strong> 子数组，<strong>至少</strong> 需要满足以下条件之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子数组的长度为 1 ，或者</li>\n",
    "\t<li>子数组元素之和 <strong>大于或等于</strong>&nbsp; <code>m</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你可以将给定数组拆分成 <code>n</code> 个满足要求的数组，返回 <code>true</code><em> </em>；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>子数组是数组中的一个连续非空元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2, 2, 1], m = 4\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "第 1 步，将数组 nums 拆分成 [2, 2] 和 [1] 。\n",
    "第 2 步，将数组 [2, 2] 拆分成 [2] 和 [2] 。\n",
    "因此，答案为 true 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2, 1, 3], m = 5 \n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：\n",
    "</strong>存在两种不同的拆分方法：\n",
    "第 1 种，将数组 nums 拆分成 [2, 1] 和 [3] 。\n",
    "第 2 种，将数组 nums 拆分成 [2] 和 [1, 3] 。\n",
    "然而，这两种方法都不满足题意。因此，答案为 false 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2, 3, 3, 2, 3], m = 6\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "第 1 步，将数组 nums 拆分成 [2, 3, 3, 2] 和 [3] 。\n",
    "第 2 步，将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。\n",
    "第 3 步，将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。\n",
    "第 4 步，将数组 [3, 3] 拆分成 [3] 和 [3] 。\n",
    "因此，答案为 true 。 </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-it-is-possible-to-split-array](https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-it-is-possible-to-split-array](https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2, 2, 1]\\n4', '[2, 1, 3]\\n5', '[2, 3, 3, 2, 3]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        return len(nums) <= 2 or any(x + y >= m for x, y in pairwise(nums))\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) <= 2:\n",
    "            return True\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]+nums[i+1] >= m:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        return len(nums) <= 2 or any(x + y >= m for x, y in pairwise(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        arr = [nums[0]] * n\n",
    "        for i in range(1, n):\n",
    "            arr[i] = arr[i - 1] + nums[i]\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for k in range(i + 2, n):\n",
    "                if (k == i + 2) and not (arr[k] - arr[i] >= m or arr[k - 1] - arr[i] + nums[i] >= m):\n",
    "                    dp[i][k] = False\n",
    "                elif k != i + 2:\n",
    "                    dp[i][k] = dp[i + 1][k] or dp[i][k - 1]\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        #区间DP非常经典的题目\n",
    "        presum=list(accumulate(nums,initial=0))\n",
    "        n=len(nums)\n",
    "        dp=[[False]*n for _ in range(n)]\n",
    "        #考虑DP数组初始化\n",
    "        for i in range(n):\n",
    "            dp[i][i]=True\n",
    "        #dp[i][j]表示nums[i:j+1]这段子数组能否拆分数组\n",
    "        #枚举长度\n",
    "        for length in range(2,n+1):\n",
    "            #枚举起点\n",
    "            for i in range(n-length+1):\n",
    "                j=i+length-1\n",
    "                #枚举分割点,考虑状态转移\n",
    "                for k in range(i,j):\n",
    "                    if (k==i or presum[k+1]-presum[i]>=m) and (k==j-1 or presum[j+1]-presum[k+1]>=m):\n",
    "                        dp[i][j]=dp[i][j] or (dp[i][k] and dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) <= 2:\n",
    "            return True\n",
    "        visited = {}\n",
    "        sums = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            sums[i] = sums[i - 1] + nums[i - 1]\n",
    "\n",
    "        return self.dfs(nums, m, 0, len(nums), visited, sums)\n",
    "\n",
    "    def dfs(self, nums, m, start, end, visited, sums):\n",
    "        if end - start == 1:\n",
    "            return True\n",
    "        if sums[end] - sums[start] < m:\n",
    "            return False\n",
    "        if (start, end) in visited:\n",
    "            return visited[(start, end)]\n",
    "\n",
    "        for i in range(start + 1, end):\n",
    "            res1 = self.dfs(nums, m, start, i, visited, sums)\n",
    "            res2 = self.dfs(nums, m, i, end, visited, sums)\n",
    "            if res1 and res2:\n",
    "                visited[(start, end)] = True\n",
    "                return True\n",
    "        visited[(start, end)] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if i + 1 == j:\n",
    "                return 2\n",
    "\n",
    "            res = 0\n",
    "\n",
    "            if prefix[j + 1] - prefix[i + 1] >= m:\n",
    "                res = max(res, dfs(i + 1, j) + 1)\n",
    "\n",
    "            if prefix[j] - prefix[i] >= m:\n",
    "                res = max(res, dfs(i, j - 1) + 1)\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        prefix = list(accumulate(nums, initial=0))\n",
    "\n",
    "        res = dfs(0, n - 1)\n",
    "\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return res == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) <=2:\n",
    "            return True\n",
    "        pre = [0] + nums\n",
    "        for i in range(1, len(pre)):\n",
    "            pre[i] = pre[i-1] + nums[i-1]\n",
    "        @lru_cache\n",
    "        def helper(i, j):\n",
    "            if i == j:\n",
    "                return True\n",
    "            if pre[j+1] - pre[i] <m:\n",
    "                \n",
    "                return False\n",
    "            return helper(i+1, j) or helper(i, j-1)\n",
    "        \n",
    "        return helper(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "    @lru_cache\n",
    "    def dfs(aL, aR, aS):\n",
    "      if aR - aL <= 1:\n",
    "        return True\n",
    "      else:\n",
    "        lv, rv = nums[aL], nums[aR]\n",
    "        ll, rl = aS - lv, aS - rv\n",
    "        if ll >= m and rl >= m:\n",
    "          return dfs(aL + 1, aR, ll) or dfs(aL, aR - 1, rl)\n",
    "        elif ll >= m:\n",
    "          return dfs(aL + 1, aR, ll)\n",
    "        elif rl >=m:\n",
    "          return dfs(aL, aR - 1, rl)\n",
    "        else:\n",
    "          return False\n",
    "    return dfs(0, len(nums) - 1, sum(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param m:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        g_ok = False\n",
    "        if len1 == 1:\n",
    "            return True\n",
    "        sp = {}\n",
    "        cache = 0\n",
    "        for k,v in enumerate(nums):\n",
    "            cache += v\n",
    "            sp[k] = cache\n",
    "        sp[-1] = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check_ok(l, r):\n",
    "            nonlocal g_ok\n",
    "            if g_ok:\n",
    "                return True\n",
    "\n",
    "            if l == r:\n",
    "                return True\n",
    "            self_ok = False\n",
    "            for i in range(l, r):\n",
    "\n",
    "                lok, rok = False, False\n",
    "                if i == l:\n",
    "                    lok = True\n",
    "                if sp[i] - sp[l-1] >= m:\n",
    "                    lok = True\n",
    "                if i + 1 == r:\n",
    "                    rok = True\n",
    "                if sp[r] - sp[i] >= m:\n",
    "                    rok = True\n",
    "                if lok and rok:\n",
    "                    v1 = check_ok(l,i)\n",
    "                    v2 = check_ok(i+1,r)\n",
    "                    if v1 and v2:\n",
    "                        self_ok = True\n",
    "                    if r -l +1 == len1 and v1 and v2:\n",
    "                        g_ok = True\n",
    "                        break\n",
    "            return self_ok\n",
    "\n",
    "        check_ok(0, len1-1)\n",
    "        check_ok.cache_clear()\n",
    "        return g_ok\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.check = dict()\n",
    "\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "\n",
    "        res = False\n",
    "        lsum = 0\n",
    "        rsum = sum(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            \n",
    "            left, right = nums[:i], nums[i:]\n",
    "            lsum += nums[i-1]\n",
    "            rsum -= nums[i-1]\n",
    "            if (len(left)>1 and lsum<m) or (len(right)>1 and rsum<m):\n",
    "                continue\n",
    "            tl, tr = tuple(left), tuple(right)\n",
    "            if tl in self.check:\n",
    "                ll = self.check[tl]\n",
    "            else:\n",
    "                ll = self.canSplitArray(left, m)\n",
    "                self.check[tl] = ll\n",
    "            if tr in self.check:\n",
    "                rr = self.check[tr]\n",
    "            else:\n",
    "                rr = self.canSplitArray(right, m)\n",
    "                self.check[tr] = rr\n",
    "            \n",
    "            if ll and rr:\n",
    "                res = True\n",
    "                break\n",
    "        return res\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) <= 2:\n",
    "            return True\n",
    "        dp = [[-1 for _ in range(len(nums))] for _ in range(len(nums))]\n",
    "        def process(nums, L, R, m):\n",
    "            if R - L == 2:\n",
    "                if (nums[L] + nums[L+1]) >= m or (nums[L+1] + nums[L+2]) >= m:\n",
    "                    dp[L][R] = True\n",
    "                    return True \n",
    "                else:\n",
    "                    dp[L][R] = False\n",
    "                    return False\n",
    "            if dp[L][R] != -1:\n",
    "                return dp[L][R]\n",
    "            p1 = process(nums, L+1, R, m)\n",
    "            p2 = process(nums, L, R-1, m)\n",
    "            dp[L][R] = p1 or p2\n",
    "            return p1 or p2\n",
    "\n",
    "        return process(nums, 0, len(nums)-1, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        preSum = [0]\n",
    "        for i in nums:\n",
    "            preSum.append(preSum[-1] + i)\n",
    "        length = len(nums)\n",
    "        tag = [[-1 for _ in range(length)] for _ in range(length)]\n",
    "\n",
    "        def dp(start, end, m, preSum):\n",
    "            if start > end:\n",
    "                return False\n",
    "            if start == end:\n",
    "                return True\n",
    "            if preSum[end + 1] - preSum[start] < m:\n",
    "                return False\n",
    "            if tag[start][end] != -1:\n",
    "                return tag[start][end]\n",
    "            res = False\n",
    "            for i in range(start, end):\n",
    "                left = dp(start, i, m, preSum)\n",
    "                right = dp(i + 1, end, m, preSum)\n",
    "                if left and right:\n",
    "                    res = True\n",
    "                    break\n",
    "            tag[start][end] = res\n",
    "            return res\n",
    "\n",
    "        return True if length == 2 else dp(0, length - 1, m, preSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):dp[i][i] = 1\n",
    "        for i in range(0,n-1):dp[i][i+1] = 1\n",
    "        for i in range(1,n):dp[i][i-1] = 1\n",
    "        def dfs(x,y,_sum):\n",
    "            if dp[x][y] != 0: return dp[x][y]\n",
    "            right = nums[y]\n",
    "            left = _sum - right\n",
    "            if left >= m and dfs(x,y-1,left) == 1:\n",
    "                dp[x][y] = 1\n",
    "                return 1\n",
    "            left = nums[x]\n",
    "            right = _sum - left\n",
    "            if right >= m and dfs(x+1,y,right) == 1:\n",
    "                dp[x][y] = 1\n",
    "                return 1\n",
    "            for i in range(x+1,y-1):\n",
    "                left += nums[i]\n",
    "                right -= nums[i]\n",
    "                if right < m:\n",
    "                    break\n",
    "                if left >=m and right >= m:\n",
    "                    l,r = dfs(x,i,left), dfs(i+1,y,right)\n",
    "                    if l == r == 1:\n",
    "                        dp[x][y] = 1\n",
    "                        return 1\n",
    "            dp[x][y] = -1\n",
    "            return 0\n",
    "        dfs(0,n-1,sum(nums))\n",
    "        return True if dp[0][n-1] == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        #n = len(nums)\n",
    "        lst = list(accumulate(nums, initial = 0))\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if r - l <= 1: return True\n",
    "            '''\n",
    "            ans = False\n",
    "            if sum(nums[l + 1 : r + 1]) >= m: ans = ans or dfs(l + 1, r)\n",
    "            if sum(nums[l : r]) >= m: ans = ans or dfs(l, r - 1)\n",
    "            for i in range(l + 2, r - 1):\n",
    "                 if sum(nums[l:i]) >= m and sum(nums[i:r + 1]) >= m: \n",
    "                     ans = ans or (dfs(l, i) and dfs(i, r))\n",
    "            return ans\n",
    "            '''\n",
    "            '''\n",
    "            return (dfs(l + 1, r) if sum(nums[l + 1 : r + 1]) >= m else False) \\\n",
    "                or (dfs(l, r - 1) if sum(nums[l : r]) >= m else False) \\\n",
    "                or any(dfs(l, i) and dfs(i, r) for i in range(l + 2, r - 1) if sum(nums[l:i]) >= m and sum(nums[i:r + 1]) >= m)\n",
    "            '''\n",
    "            return (dfs(l + 1, r) if lst[r + 1] - lst[l + 1] >= m else False) \\\n",
    "                or (dfs(l, r - 1) if lst[r] - lst[l] >= m else False) \\\n",
    "                or any(dfs(l, i) and dfs(i, r) for i in range(l + 2, r - 1) if lst[i] - lst[l] >= m and lst[r + 1] - lst[i] >= m)                \n",
    "        return dfs(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def f(i: int, j: int) -> bool:\n",
    "            if i == j - 1:\n",
    "                return True\n",
    "            return any(f(i, x) and f(x, j) for x in range(i + 1, j) if (x == i + 1 or sum(nums[i:x]) >= m) and (x == j - 1 or sum(nums[x:j]) >= m))\n",
    "        return f(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) <= 2:\n",
    "            return True\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            elif i + 1 == j:\n",
    "                return nums[i] + nums[j] >= m\n",
    "\n",
    "            for idx in range(i, j):\n",
    "                if nums[idx] + nums[idx + 1] >= m:\n",
    "                    val = dfs(i, idx - 1) or dfs(idx + 2, j)\n",
    "                else:\n",
    "                    val = dfs(i, idx) and dfs(idx + 1, j)\n",
    "                if val:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        csum = [0]\n",
    "        t = 0\n",
    "        for num in nums:\n",
    "            t += num\n",
    "            csum.append(t)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(i: int, j: int) -> bool:\n",
    "            if i == j - 1:\n",
    "                return True\n",
    "            return any(f(i, x) and f(x, j) for x in range(i + 1, j) if (x == i + 1 or csum[x] - csum[i] >= m) and (x == j - 1 or csum[j] - csum[x] >= m))\n",
    "        return f(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        accs = [0]\n",
    "        for num in nums:\n",
    "            accs.append(accs[-1] + num)\n",
    "        @cache\n",
    "        def check(i, j):\n",
    "            nonlocal m\n",
    "            if i + 1 >= j:\n",
    "                return True\n",
    "            for k in range(i, j):\n",
    "                c1 = (i == k or (accs[k+1] - accs[i]) >= m) and check(i, k)\n",
    "                if not c1:\n",
    "                    continue\n",
    "                c2 = (k + 1 == j or (accs[j + 1] - accs[k + 1]) >= m) and check(k + 1, j)\n",
    "                if c2:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return check(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        \n",
    "        @cache\n",
    "        def split(l: int, r: int) -> bool:\n",
    "            if r - l <= 2:\n",
    "                return True\n",
    "        \n",
    "            for i in range(1, r - l):\n",
    "                if (s[l+i] - s[l] >= m or i == 1) and (s[r] - s[l+i] >= m or r - l - i == 1) and split(l, l+i) and split(l+i, r):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "        return split(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        \n",
    "        n = len(nums)\n",
    "        pf = [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            pf[i] = pf[i-1] + nums[i-1]\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j - i <= 2:\n",
    "                return True\n",
    "            left_part = nums[i:j-1]\n",
    "            right_part = nums[i+1:j]\n",
    "            left_sum = pf[j-1] - pf[i]\n",
    "            right_sum = pf[j] - pf[i+1]\n",
    "            left_judge = left_sum >= m and dfs(i, j-1)\n",
    "            right_judge = right_sum >= m and dfs(i+1, j)\n",
    "            return left_judge or right_judge\n",
    "        \n",
    "        return dfs(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums)<=2:return True\n",
    "        s = list(accumulate(nums,initial=0))\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j==i :return True\n",
    "            if s[j+1]-s[i]<m:return False\n",
    "            return any([dfs(i,k) and dfs(k+1,j) for k in range(i,j)])\n",
    "        return dfs(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        preSums = list(accumulate(nums, initial=0))\n",
    "        @cache\n",
    "        def helper(i, j):\n",
    "            n = j - i\n",
    "            if n < 3: return True\n",
    "            midSum = preSums[j - 1] - preSums[i + 1]\n",
    "            preSum = nums[i]\n",
    "            postSum = midSum + nums[j - 1]\n",
    "            if postSum >= m:\n",
    "                if helper(i + 1, j):\n",
    "                    return True\n",
    "                for k in range(i + 1, j - 2):\n",
    "                    x = nums[k]\n",
    "                    preSum += x\n",
    "                    postSum -= x\n",
    "                    if postSum < m:\n",
    "                        break\n",
    "                    if preSum >= m and helper(i, k + 1) and helper(k + 1, j):\n",
    "                        return True\n",
    "            return midSum + nums[i] >= m and helper(i, j - 1)\n",
    "        return helper(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "\n",
    "        n = len(nums)\n",
    "        # if n <= 2:\n",
    "        #     return True\n",
    "        pres = list(accumulate(nums, initial=0))\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if r - l <= 1:\n",
    "                return True\n",
    "  \n",
    "            for j in range(l, r):\n",
    "                if (j == l or pres[j + 1] - pres[l] >= m and dfs(l, j)) and (j + 1 == r or pres[r + 1] - pres[j + 1] >= m and dfs(j + 1, r)):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        presum = [0]\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            presum.append(pre)\n",
    "        memo = {}\n",
    "        def check(i,j):\n",
    "            if(j-i+1 <= 2):\n",
    "                return True\n",
    "            if((i,j) in memo):\n",
    "                return memo[(i,j)]\n",
    "            for k in range(i,j):\n",
    "                if(k == i):\n",
    "                    if(presum[j+1]-presum[i+1] >= m and check(i+1,j)):\n",
    "                        memo[(i,j)] = True\n",
    "                        return True\n",
    "                elif(k == j-1):\n",
    "                    if(presum[j]-presum[i] >= m and check(i,j-1)):\n",
    "                        memo[(i,j)] = True\n",
    "                        return True\n",
    "                else:\n",
    "                    if(presum[k+1]-presum[i] >= m and presum[j+1]-presum[k+1] >= m and check(i,k) and check(k+1,j)):\n",
    "                        memo[(i,j)] =True\n",
    "                        return True\n",
    "            memo[(i,j)] = False\n",
    "            return False\n",
    "        return check(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        \n",
    "        # return len(nums)<=2 or any(x+y>=m for x,y in pairwise(nums))\n",
    "        @functools.lru_cache(None)\n",
    "        def fun(i, j): # 判断闭区间 i j 是否可以满足\n",
    "            if j-i > 0:\n",
    "                if sum(nums[i: j+1]) >= m:\n",
    "                    for k in range(i, j): # 遍历子区间划分\n",
    "                        if fun(i, k) and fun(k+1, j):\n",
    "                            return True # 如果某种划分可以，则整体可以\n",
    "                    return False\n",
    "                        \n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return True\n",
    "        if len(nums) == 2: # 特判\n",
    "            return True\n",
    "        return fun(0, len(nums)-1)\n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> bool:\n",
    "            if i == j:\n",
    "                return True\n",
    "            for k in range(i, j):\n",
    "                a = k == i or s[k + 1] - s[i] >= m\n",
    "                b = k == j - 1 or s[j + 1] - s[k + 1] >= m\n",
    "                if a and b and dfs(i, k) and dfs(k + 1, j):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        return dfs(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <=2:\n",
    "            return True\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i==j:\n",
    "                return True\n",
    "            if i+1 == j:\n",
    "                return nums[i] + nums[j] >= m\n",
    "            res = False\n",
    "            for k in range(i,j):\n",
    "                res = res or (f(i,k) and f(k+1,j))\n",
    "            return res\n",
    "        return f(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        cur_sum = [0] + list(accumulate(nums))\n",
    "\n",
    "        def check(left: int, right: int) -> bool:\n",
    "            return right == left + 1 or cur_sum[right] - cur_sum[left] >= m\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def helper(left: int, right: int) -> bool:\n",
    "            if right == left + 1:\n",
    "                return True\n",
    "            for idx in range(left + 1, right):\n",
    "                if check(left, idx) and check(idx, right) and helper(left, idx) and helper(idx, right):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return helper(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l == r: return True\n",
    "            if s[r+1] - s[l] < m: return False \n",
    "            \n",
    "            for i in range(l, r):\n",
    "                if dfs(l, i) and dfs(i+1, r): return True\n",
    "            return False\n",
    "        \n",
    "        n = len(nums)\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            s[i] = s[i-1] + nums[i-1]\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            if dfs(0, i) and dfs(i+1, n-1): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        \n",
    "        @cache\n",
    "        def helper(i: int, j: int) -> bool:\n",
    "            if i + 1 == j:\n",
    "                return True\n",
    "            for k in range(i + 1, j):\n",
    "                left_sum = prefix_sum[k] - prefix_sum[i]\n",
    "                right_sum = prefix_sum[j] - prefix_sum[k]\n",
    "                if (k == i + 1 or left_sum >= m) and (k == j - 1 or right_sum >= m):\n",
    "                    lhs = helper(i, k)\n",
    "                    rhs = helper(k, j)\n",
    "                    if lhs and rhs:\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        prefix_sum = list(accumulate(nums, initial=0))\n",
    "        return helper(0, len(nums))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        @cache\n",
    "        def helper(i: int, j: int) -> bool:\n",
    "            # [i, j)\n",
    "            if i + 1 == j:\n",
    "                return True\n",
    "            # 0 2\n",
    "            for k in range(i + 1, j):\n",
    "                # nums[i:k] & nums[k:j]\n",
    "                # -> i < k < j\n",
    "                left_sum = prefix_sum[k] - prefix_sum[i]\n",
    "                right_sum = prefix_sum[j] - prefix_sum[k]\n",
    "                if (k == i + 1 or left_sum >= m) and (k == j - 1 or right_sum >= m):\n",
    "                    lhs = helper(i, k)\n",
    "                    rhs = helper(k, j)\n",
    "                    if lhs and rhs:\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        prefix_sum = list(accumulate(nums, initial=0))\n",
    "        return helper(0, len(nums))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        cur_sum = [0] + list(accumulate(nums))\n",
    "\n",
    "        def check(left: int, right: int) -> bool:\n",
    "            return right == left + 1 or cur_sum[right] - cur_sum[left] >= m\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def helper(left: int, right: int) -> bool:\n",
    "            if right == left + 1:\n",
    "                return True\n",
    "            for idx in range(left + 1, right):\n",
    "                if check(left, idx) and helper(left, idx) and check(idx, right) and helper(idx, right):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return helper(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        cur_sum = [0] + list(accumulate(nums))\n",
    "\n",
    "        def check(left: int, right: int) -> bool:\n",
    "            return right == left + 1 or cur_sum[right] - cur_sum[left] >= m\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def helper(left: int, right: int) -> bool:\n",
    "            if right == left + 1:\n",
    "                return True\n",
    "            for idx in range(left + 1, right):\n",
    "                if helper(left, idx) and helper(idx, right) and check(left, idx) and check(idx, right):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return helper(0, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        pre = list(itertools.accumulate(nums, initial=0))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> bool:\n",
    "            if j - i <= 1:\n",
    "                return True\n",
    "            for k in range(i, j):\n",
    "                if (\n",
    "                    dfs(i, k)\n",
    "                    and (i == k or pre[k + 1] - pre[i] >= m)\n",
    "                    and dfs(k + 1, j)\n",
    "                    and (k + 1 == j or pre[j + 1] - pre[k + 1] >= m)\n",
    "                ):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, len(nums) - 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        cs = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            cs += num\n",
    "            nums[i] = cs\n",
    "        def getsum(i, j):\n",
    "            if i <= 0:\n",
    "                return nums[j-1]\n",
    "            else:\n",
    "                return nums[j-1] - nums[i-1]\n",
    "        @lru_cache(None)\n",
    "        def cansplit_and_cansplitfrom(i, j):\n",
    "            print(i, j)\n",
    "            if j-i <= 2:\n",
    "                return True, j-i == 1 or getsum(i, j) >= m\n",
    "            if getsum(i ,j) < m:\n",
    "                return False, False\n",
    "            k = j-1\n",
    "            while k > i:\n",
    "                a, b = cansplit_and_cansplitfrom(i, k)\n",
    "                c, d = cansplit_and_cansplitfrom(k, j)\n",
    "                if a and b and c and d:\n",
    "                    return True, True\n",
    "                if not b:\n",
    "                    k = min(k, i+2)\n",
    "                k -= 1\n",
    "            return False, True\n",
    "        return cansplit_and_cansplitfrom(0, len(nums))[0]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        # s = list(accumulate(nums, initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j: return True\n",
    "            for k in range(i, j):\n",
    "                if dfs(i, k) and (k == i or sum(nums[i: k + 1]) >= m) and dfs(k + 1, j) and (k + 1 == j or sum(nums[k + 1: j + 1]) >= m):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l == r: return True\n",
    "            if s[r+1] - s[l] < m: return False\n",
    "            \n",
    "            for i in range(l, r):\n",
    "                if dfs(l, i) and dfs(i+1, r): return True\n",
    "            return False\n",
    "        \n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        \n",
    "        for i in range(len(nums)-1):\n",
    "            if dfs(0, i) and dfs(i+1, len(nums) - 1): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        start = False\n",
    "        @cache\n",
    "        def dfs(l: int, r: int) -> bool:\n",
    "            nonlocal start\n",
    "            nonlocal nums\n",
    "            if l == r:\n",
    "                return True\n",
    "            if start and sum(nums[l: r + 1]) < m:\n",
    "                return False\n",
    "            start = True\n",
    "            for i in range(l, r):\n",
    "                if dfs(l, i) and dfs(i + 1, r):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "        return dfs(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        n = len(nums)\n",
    "        l = [0] * n\n",
    "        l[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            l[i] = l[i - 1] + nums[i]\n",
    "\n",
    "        @cache\n",
    "        def bt(i, j):\n",
    "            if i == j:\n",
    "                return 1\n",
    "            elif l[j] - l[i] + nums[i] < m:\n",
    "                return 0\n",
    "            else:\n",
    "                for k in range(i, j):\n",
    "                    if bt(i, k) == 1 and bt(k + 1, j) == 1:\n",
    "                        return 1\n",
    "                return 0\n",
    "\n",
    "        if n <= 2:\n",
    "            return True\n",
    "        else:\n",
    "            return bt(0, n - 1) == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        s=sum(nums)\n",
    "        n=len(nums)\n",
    "        l=0\n",
    "        r=n-1\n",
    "        @cache\n",
    "        def dfs(l,r,s):\n",
    "            if l+1==r:\n",
    "                if s>=m:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if dfs(l+1,r,s-nums[l]) or dfs(l,r-1,s-nums[r]):\n",
    "                return True\n",
    "            return False\n",
    "        if n<=2:\n",
    "            return True\n",
    "        return dfs(0,n-1,s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSplitArray(self, nums: List[int], m: int) -> bool:\n",
    "        sum = 0\n",
    "        for x in nums:\n",
    "            sum += x\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, total):\n",
    "            if j - i + 1 <= 2:\n",
    "                return True\n",
    "            res = False\n",
    "            if total - nums[i] >= m:\n",
    "                res = res or dfs(i + 1, j, total - nums[i])\n",
    "            if total - nums[j] >= m:\n",
    "                res = res or dfs(i, j - 1, total - nums[j])\n",
    "            return res    \n",
    "\n",
    "        return dfs(0, len(nums) - 1, sum)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
